package codingforgreat.lchot150;

public class Lc378 {
    class Info{
        int near;
        int num;
        public Info(int ne,int n){
            near = ne;
            num = n;
        }
    }
    public int kthSmallest(int[][] matrix, int k) {
        int l = matrix[0][0];
        int N = matrix.length;
        int M = matrix[0].length;
        int r = matrix[N - 1][M - 1];
        int ans = 0;
        int m = 0;
        while(l <= r){
            m = (l + r) / 2;
            Info info = getInfo(matrix,m);
            if(info.num > k){
                ans = info.near;
                r = m - 1;
            }else if(info.num < k){
                l = m + 1;
            }else{
                return info.near;
            }
        }
        return ans;
    }
    public Info getInfo(int[][] matrix,int k){
        int N = matrix.length;
        int M = matrix[0].length;
        int j = M - 1;
        int i = 0;
        int ans = 0;
        int res = Integer.MIN_VALUE;
        while( i < N && j >= 0){
            if (matrix[i][j] <= k) {
                res = Math.max(res, matrix[i][j]);
                ans += j + 1;
                i++;
            } else {
                j--;
            }
        }
        return new Info(res,ans);
    }
}
